package traverse

import "../binarytree"

// import "encoding/binary"

type TreeNode = binarytree.TreeNode

// 层次遍历
func levelOrder(root *TreeNode) [][]int {
	if root == nil {
		return nil
	}
	queue := []*TreeNode{root}
	var res [][]int
	var curNode *TreeNode
	for len(queue) > 0 {
		curLevelWidth := len(queue)
		curLeveNodes := []int{}
		for i := 0; i < curLevelWidth; i++ {
			curNode = queue[0]
			queue = queue[1:] //出队
			// 访问
			curLeveNodes = append(curLeveNodes, curNode.Val)
			// 左右子节点入队
			if curNode.Left != nil {
				queue = append(queue, curNode.Left)
			}
			if curNode.Right != nil {
				queue = append(queue, curNode.Right)
			}
		}	
		// 该层存储res
		res = append(res, curLeveNodes)
	}
	return res
}
